数据结构:链表应用:第8关:链表的逆转 | 您所在的位置:网站首页 › 倒置链表 数据结构头歌 › 数据结构:链表应用:第8关:链表的逆转 |
任务描述编程要求
输入输出测试说明来源
任务描述
本关任务:利用单链表表示一个整数序列,通过一趟遍历,将单链表中所有结点的链接方向逆转。要求空间复杂度为O(1)。 编程要求 输入多组数据,每组数据有两行,第一行为链表的长度n,第二行为链表的n个元素(元素之间用空格分隔)。当n=0时输入结束。 输出对于每组数据分别输出一行,逆序输出链表中的元素,元素之间用空格分隔。 测试说明平台会对你编写的代码进行测试: 测试输入: 5 1 2 3 4 5 6 3 1 2 5 4 6 0 预期输出: 5 4 3 2 1 6 4 5 2 1 3 来源BJFUOJ 开始你的任务吧,祝你成功 关键在于L->next,也就是头结点的指针域。它在循环的过程中,始终指向逆置的结点(也就是需要改向的,那个结点的前一个),循环过程中p与q每次逆置向后移一位 #include using namespace std; typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; void CreateList_R(LinkList &L,int n) { L->next=NULL; LinkList r=new LNode; r=L; for(int i=0;i>p->data; p->next=NULL; r->next=p; r=p; } } void Inverse(LinkList &L) {//逆置带头结点的单链表L /**************begin************/ if(L == NULL || L->next == NULL) return; // 如果链表为空或只有一个节点,无需逆置,直接返回 a. LinkList p = L->next, q; // 初始化p指向第一个节点 L->next = NULL; // 将头节点的next置为NULL 1. while(p ) { q = p->next; // 保存p的下一个节点 2. p->next = L->next; // 修改p的next指向 L->next = p; // 修改头节点的next指向 3. p = q; // p移动到下一个节点 } /**************end************/ } void PrintList(LinkList &L) { L=L->next; while(L){ if(L->next!=NULL) cout |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |